package com.liunian.algorithmstudy.dynamic.completebackpack;

import java.util.Scanner;

public class TakeSearch {

	/**
	 小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，
	 但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，
	 并且具有不同的价值。小明的行李箱所能承担的总重量是有限的，问小明应该如何抉择，才能携带最大价值的研究材料，
	 每种研究材料可以选择无数次，并且可以重复选择。

	 输入描述
	 第一行包含两个整数，n，v，分别表示研究材料的种类和行李所能承担的总重量
	 接下来包含 n 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值

	 输出描述
	 输出一个整数，表示最大价值。

	 输入示例
	 4 5
	 1 2
	 2 4
	 3 4
	 4 5
	 输出示例
	 10
	 提示信息
	 第一种材料选择五次，可以达到最大值。

	 数据范围：

	 1 <= n <= 10000;
	 1 <= v <= 10000;
	 1 <= wi, vi <= 10^9.
	 */

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		// 物品种类
		int n = scan.nextInt();
		// 背包重量
		int v = scan.nextInt();
		int[] weight = new int[n];
		int[] value = new int[n];
		for (int i = 0; i < n; i++) {
			weight[i] = scan.nextInt();
			value[i] = scan.nextInt();
		}
		int[][] dp = new int[n][v + 1];
		for (int i = 0; i <= v; i++) {
			dp[0][i] = (i / weight[0]) * value[0];
		}
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= v; j++) {
				if (j < weight[i]) {
					dp[i][j] = dp[i - 1][j];
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
				}
			}
		}
		System.out.println(dp[n - 1][v]);
	}

}
